package demo1;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {


    //统计不是特殊数字的数字量
    public int nonSpecialCount(int l, int r) {
        int l_ = (int) Math.ceil(Math.sqrt(l)), r_ = (int) Math.floor(Math.sqrt(r));
        if (r_ < l_) return r - l + 1;
        int primeL = olaSieve(l_-1), primeR = olaSieve(r_);
        return (r - l + 1) - (primeR - primeL);
    }

    private int olaSieve(int n) {
        if (n <= 0) return 0;
        boolean[] st = new boolean[n+1];
        List<Integer> primes = new ArrayList<>();
        st[0] = true;
        st[1] = true;
        int res = 0;
        for (int i = 2; i <= n; i++) {
            // 将素数存入 primes
            if (!st[i]) {
                primes.add(i);
                res++;
            }
            for (int j = 0; primes.get(j) <= n/i; j++) {
                st[primes.get(j) * i] = true;
                if (i % primes.get(j) == 0) break;
            }
        }
        return res;
    }
}
